The present invention relates to the scan conversion, or pixel rendering, of outline fonts and other graphic elements with anti-aliasing.
Many of the images used to communicate information today are pixel images, that is, images comprised of an array of discrete pixels, or picture elements. Displays on computer screens are normally created using pixel images. In computer displays a pixel normally represents the smallest portion of the display""s screen which can be used to show a complete color value. In a monochrome display, a pixel is normally the smallest area the display is capable of illuminating or not. In color displays, a pixel is often the smallest area of the screen which the display can cause to output a composite color. Usually the composite color is formed from sub-pixels, such as a set of red, green, and blue sub-pixels, which are combined to define one full color pixel.
Many printed images are also created as pixel images. In two tone printed images each pixel often represents the smallest mark the printer can make on a piece of paper. In grayscale printed images, a pixel often represents the smallest region on which the printer creates a complete dot pattern having any one of the different grayscale values used to produce grayscale images. In color printed images a full color pixel is created by combining separate grayscale sub-pixels in each of a set of basic colors such as cyan, magenta, yellow, and black.
Many bitmap images are merely displays of information stored in bitmap form having a color value (where color value can represent white or black, a greyscale, or a composite color value) associated with each pixel to be displayed. The computation involved in displaying such bitmap requires little more than moving its pixel values from the bitmap to the portion of computer memory used to represent the screen image. If the display on the screen is at a higher or a lower resolution than that of the given bitmap, all that is required is to re-scale the bitmap to the desired size and to adjust the color values of any partially covered pixels of the resulting image in proportion to the extent they are covered by the re-scaled bitmap.
On the other hand, many bitmap""s displayed on computer screens or in printed output are produced from descriptions of shapes to be rendered which are described at a substantially higher resolution than the size of the pixels of bitmapped image to be displayed. In such cases, an algorithm is required to convert such high resolution descriptions into an appropriate pixel image of the shapes they describe. This is particularly common with, so-called, scalable fonts. Scalable fonts are character fonts, the shapes of which are precisely described at a high resolution in terms of lines and curves. Because of this, the shape of a given character in the font can be displayed over a wide ranges of different sizes merely by expanding or contracting the projection of the character""s precise description into a given pixel image.
In this specification and the claims which follow, reference to shapes which are defined at a higher or finer resolution than the resolution of a pixel image refer to shapes with definitions which are capable of specifying the boundaries of such shapes at a resolution higher than that of the pixel image. The high resolution referred to is the resolution of the shape defined, not necessarily that of the points or numbers used in the formula or statement which defines such a shape. For example, one could define an outline font in which all the points used as endpoints or control points in the formula or statement used to describe a character""s curves or line segments occur on corners of the pixel grid of a given pixel image. In such a case, the points used to describe the font shape would have the same resolution as the pixel image, but if the character shapes include any curved or diagonal lines, the resolution of the shape described by such lines would be much higher than that of the pixel image.
FIG. 1 illustrates the word xe2x80x9cBitstreamxe2x80x9d 100, the name of the assignee of the present invention, with the shape of its letters 102 described in a high resolution outline, causing those outlines to appear smooth.
FIG. 2 illustrates how the shapes of the characters 102 in FIG. 1 begin to look more jagged when they are displayed at a pixel resolution lower than the resolution of the outline description.
FIG. 3 is a close-up of the portion of the pixel image of FIG. 2 shown in the dotted box 108. In FIG. 3 individual pixels 110 of the pixel image are shown. The pixels of the image shown in FIG. 3 are arranged in perpendicular rows 112 and columns 114, as is commonly the case in video displays.
In FIG. 3 the letter capital xe2x80x9cBxe2x80x9d is shown to have three outlines 113A, 113B, and 113C and the letter small xe2x80x9cixe2x80x9d has two outlines 113D and 113E.
FIG. 4 shows the outlines 113A-113E in dotted lines superimposed on top of a pixel image corresponding to the shapes defined by those outlines. This pixel image corresponds to the image of xe2x80x9cBixe2x80x9d shown within the dotted box 108 in FIG. 2.
As can be seen from FIG. 4, the process of converting high resolution outlines, such as the outlines 113A-113E, to a lower resolution pixel image often produces images with jagged edges such as the jagged edges 118 shown in FIG. 4.
It is well-known in the prior art that one can make the edges of a pixel images appear to human viewers to be more smooth by using a process known as anti-aliasing. Anti-aliasing is the process of causing pixels which are partially covered by higher resolution shape being rendered to have intermediate covered values, as is shown by the grayscale pixels 120 shown in FIG. 5.
FIG. 6 is identical to FIG. 5 except that it shows the pixel image of FIG. 5 without the grid of individual pixels 110 being shown.
Anti-aliasing commonly seeks to assign a coverage value, also knows as a color or grayscale value, to a partially covered pixel which is proportional to the percent of the pixel which is covered by one or more high resolution shapes. This is indicated in FIG. 7 in which a pixel 110 is shown partially covered by shape 114.
It is possible to take the geometric definition of a shape provided by an outline font description and used geometric methods to calculate the exact percentage of the pixel 110, shown in FIG. 7, covered by that shape. Once this has been done a coverage value corresponding to that percentage can be assigned to the pixel for purposes of anti-aliasing. Unfortunately such computations require a fair amount of processing, which can make rendering a large number of characters with such exactly calculated anti-aliasing undesirably slow. As a result it has been common to calculate the coverage values of partially covered pixels by using approximation.
FIG. 8 illustrates one such approximation method. In this method the curves in the outline description of a shape 114 being rendered are approximated with a series of corresponding linear segments 122. Such an approximation is considerably faster than trying to calculate the exact area of the shape 114.
FIG. 9 shows another prior-art approximation method. This method includes determining for each of an array of points 124 located within the pixel 110 whether or not that point falls within the shape 114 or not. It then assigns a coverage value to the pixel which is a function of the proportion of such points within the pixel which fall within the shape 114 relative to which do not.
FIG. 10 illustrates an approximation method which is been previously used by the inventor of the present application. According to this method, each pixel has associated with it one to five horizontal sampling lines 126 and one to five vertical sampling lines 128. A determination is made for each sampling line of what percent of that line is covered by the shape 114. Then pixel 110 is assigned a coverage value which equals the average of the coverage values for each of the four sampling lines.
The program used in this earlier method allowed OEM""s who licensed it to set the number of both horizontal and vertical scan lines to any value between one and five. But the inventor found than using less than the three sampling lines in both directions shown in FIG. 10 tended to product poor results, and, thus, he recommended to such licensees that they use at least three sampling lines in each direction.
All the above methods produce acceptable anti-aliasing for use in pixel images. The approximations described above with regard to FIGS. 8, 9, and 10 normal produce considerable improvements in the speed of rendering anti-aliased images. Nevertheless it is desirable to produce even faster approximation methods for assigning pixel coverage values to partially covered pixels.
It is an object of the present invention to provide apparatuses, methods, and media for more rapidly assigining pixel coverage values to the pixels of an anti-aliased bitmap image.
It is yet another object of the present invention to provide such apparatuses, methods, and media which provides a fairly accurate assignment of such pixel coverage values given the reduction in computation which they make possible.
According to a first aspect of the invention a computerized method is provided for setting pixel coverage values in a 2-diminsional pixel image for use in human-readable displays. The 2-dimensional pixel image represents a higher-resolution 2-dimensional representation of one or more shapes, such as those of fonted characters or of graphic designs, defined at a finer resolution than the resolution of the pixel image. The pixel image is formed of a plurality of pixels, each representing a corresponding sampling area of the higher-resolution representation and each having a pixel coverage value indicating the extent to which the corresponding sampling area is covered by one of the shapes.
According to this first aspect of the invention, the method performs the following for each of a plurality of the pixels of the image: determining a line coverage value for each of at least two sampling lines running in different directions within the pixel""s corresponding sampling area as a function of the degree to which the sampling line is covered by any of the shapes within the sampling area; and determining the pixel coverage value for the pixel as a non-linear function of the line coverage values determined for the two sampling lines.
In many embodiments of this first aspect of the invention, over a majority of the possible different combinations of line coverage values for the two sampling lines running in different directions produced by the method, the rate of change of the pixel coverage value varies more rapidly with variations in the line coverage value of that one of the two sampling lines whose line coverage value is nearest a value associated with one half of the sampling line being covered by such shapes.
In some such embodiments, over a majority of possible different combinations of line coverage values for the two sampling lines, the rate of change of the pixel coverage value varies only in response to the line coverage value of that one of the two sampling lines which is nearest being one-half covered by shapes being rendered.
In other of such embodiments, over a majority of possible different combinations of line coverage values for the two sampling lines, the rate of change of the pixel coverage value varies in response to variations in the line coverage values of both of the two sampling lines.
In some embodiments of this first aspect of the invention the non-linear function used to determine pixel coverage values determines those value by looking up a value in a look-up table at a location addressed as a function of the line coverage values of the two sampling lines. The values in the look-up table for a given combination of line coverage values can be derived from a plurality of pixel coverage value calculations made by a more computationally accurate and intensive method in prior situations in which a pixel had a corresponding combination of line coverage values.
Where the shapes being rendered are characters in different sets of fonts, different look-up tables can be used to determine the pixel coverage value when rendering characters from the different sets of fonts.
In some embodiments of this first aspect of the invention the non-linear function determines a pixel coverage value as a function involving a weighted sum of the line coverage values of the two sampling lines running in different directions. In this weighted sum, the contribution of each of the two line coverage values is a function of how close each such line coverage value is to an intermediate line coverage value.
In some embodiments of this first aspect of the invention the two sampling lines running in different directions are at right angles to each other. In some such embodiments the pixel image is comprised of pixels arranged in rows and columns, and the coverage values are determined for only two sampling lines in each pixel, one sampling line extending in substantially in the middle of each pixel row and one sampling line extending in substantially the middle of each pixel column.
In many embodiment of this first aspect of the invention the shapes being rendered are described by outlines which define the shapes at a higher resolution than the pixel resolution of the pixel image, and the line coverage values are determined as a function of the distance between intersections of shape outlines and the sampling lines.
According to a second aspect of the invention, a computerized method for creating a 2-diminsional pixel image for use in human-readable displays is provided which uses two pixel setting passes. The pixel image represents a higher-resolution 2-dimensional representation of one or more shapes defined at a finer resolution than the resolution of the pixel image. The pixel image is formed of a plurality of pixels, each representing a corresponding sampling area of the higher-resolution representation and each having a pixel coverage value indicating the extent to which the corresponding sampling area is covered by one of the shapes
This second, two-pass, aspect of the invention includes the following: calculating the intersections between the shapes and a first set of parallel sampling line running in a first direction in the higher-resolution representation; calculating the intersections between the shapes and a second set of parallel sampling line running in a second direction, different than the first direction, in the higher-resolution representation; and performing a first and a second pixel setting pass.
The first pixel setting pass includes calculating a pixel coverage value for each pixel by: determining the line coverage values of the one or more sampling lines of the first set in the pixel""s sampling area as a function of the degree to which such sampling line are covered by any of the shapes within the sampling area; and then determining the pixel coverage value for the pixel as a function of such line coverage values.
The second pixel setting pass is performed after the first and it only changes pixel coverage values set in the first pass for pixels presenting a sampling area in which one or more of the intersections between the shapes and the second set of sampling lines have been calculated. The second pass changes the pixel coverage value of a pixel in which such an intersection has been calculated by: determining the line coverage values of the one or more sampling lines of the second set in the pixel""s sampling area as a function of the degree to which such sampling line are covered by any of the shapes within the sampling area; and then determining the pixel coverage value for the pixel as a function of the line coverage values calculated for the pixel in the first pass and the line coverage values calculated for the pixel in the second pass.
In some embodiments of this second, two-pass, aspect of the invention the pixel image is comprised of a series of pixel rows stored in a memory at sequential addresses, and each pixel row includes a series of pixel coverage values stored in the memory at even more closely spaced sequential addresses. In such embodiments the first pixel setting pass is performed for sampling lines which extend in the direction of such pixel rows. In many such embodiments, the pixel image is comprised of a two dimensional array of pixels, and the first and second directions correspond to the two dimensions of the array.
In some embodiments of this two-pass aspect of the invention the second pixel-setting pass causes the pixel coverage value for a pixel to be determined as a non-linear function of the line coverage values of sampling lines running in the first and second directions. In this non-linear function the rate at which the pixel coverage value changes as a function of the rate of change in a given line coverage value varies as a function of the line coverage value itself.
According to a third aspect of the invention a two-pass method for creating a 2-dimentionsal pixel image is provided which is similar to the two-pass method of the second aspect of the invention. According to this third aspect of the invention the shapes being rendered are character-font shapes defined by outlines at a finer resolution than the resolution of the pixel image and the pixels of the image are arranged in rows and columns. The first set of lines run along pixel rows and the second set run along pixel columns. The method advances around each outline of a character-font shape being rendered to find each intersection between that outline and the row and column lines. Each such intersection found is placed in an ordered intersection list associated with the sampling line with which the intersection occurred, with the order of intersections in the list reflecting the order of the intersection along the list""s associated sampling line.
The first pixel setting pass of the third aspect of the invention includes a loop performed for each pixel row. In this loop, for each pixel in the row if there is no intersection in the list associated with the row""s sampling line which occurs within the pixel""s sampling area, the pixel is set to a pixel coverage value corresponding to the sampling line""s current line coverage state, either all covered or all uncovered. Otherwise the following steps are taken: 1) the sampling line""s current line coverage state is changed to reflect each of one or more successive intersections in the intersection list which occurs within the pixel""s sampling area; 2) a row line coverage value is calculated as a function of the percentage of the row sampling line within the pixel""s sampling area which is covered by any character-font shapes; and 3) the pixel is set to a pixel coverage value determined as a function of the row line coverage value calculated for the pixel.
The second pixel setting pass performed in the third aspect of the invention after the first pixel setting pass, includes a loop performed for each pixel column with any intersections in its associated intersection list. In this loop, for each pixel in the column having an intersection in its intersection list which occurs in the pixel""s sampling area the following steps are performed: 1) changing the column sampling line""s current line coverage state to reflect each successive intersection in the intersection list within the pixel""s sampling area; 2) calculating a column line coverage value as a function of the percentage of the column sampling line within the pixel""s sampling area which is covered by the character-font shape; and 3) setting the pixel""s pixel coverage value as a function of the row line coverage value calculated for the pixel in the first pixel-setting pass and the column line coverage value calculated for the pixel in the second pixel-setting pass.
In many embodiments of this third aspect of the invention the function used to set pixel coverage values in the second pixel-setting pass is a non-linear function in which, over a majority of possible different combinations of row and column line coverage values, the rate of change of the pixel coverage value varies more rapidly with variations in the line coverage value of that one of the pixel""s row or column sampling lines is nearest being one half covered by the shapes being rendered.
According to yet other aspects of the inventions, computer systems and computer programming stored in computer readable memory are provided which perform methods of the type described above.